import java.util.Stack;

public class Test {
    // 出栈入栈顺序匹配： https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
    public static boolean IsPopOrder (int[] pushV, int[] popV) {
        // write code here
        // 定义一个栈
        Stack<Integer> s=new Stack<>();

        int i=0;
        int j=0;
        for(;i<pushV.length;i++){
            // 将 pushV 中的元素放进去
            s.push(pushV[i]);
            // 判断是否相等 ，前提 栈不为空，并且j< popV 的长度
            while(!s.empty() && j< popV.length && s.peek() == popV[j]){
                s.pop();
                j++;
            }
        }

        return s.empty();
    }

    public static void main(String[] args) {
        int[] pushV={2,1,0};
        int[] popV={1,2,0};
        System.out.println(IsPopOrder(pushV, popV));
    }







    // 括号匹配：https://leetcode.cn/problems/valid-parentheses/
    public static boolean isValid(String s) {
        Stack<Character> stack=new Stack<>();
        int i=0;

        for(;i<s.length();i++){
            char c=s.charAt(i);
            if( c =='(' || c =='[' || c == '{' ){
                stack.push(c);
            }else{

                //  如果栈空，则不匹配
                if(stack.size()==0){
                    return false;
                }
                // 查看栈顶元素 看看是否匹配
                char ch=stack.peek();
                if( (ch =='('&& c ==')') || (ch =='{'&& c =='}') || (ch =='['&& c ==']') ){
                    stack.pop();
                }else{
                    return false;
                }

            }
        }
        if(stack.size() == 0 && i ==s.length()){
            return true;
        }
        return false;
    }

        /*
        Stack<Character> stack=new Stack<>();
        int i=0;

        for(;i<s.length();i++){
            char c=s.charAt(i);
            int a=0;
            if( c =='(' || c =='[' || c == '{' ){
                stack.push(c);
            }else{
                if(stack.size()==0){
                    return false;
                }
                // 查看栈顶元素 看看是否匹配
                char ch=stack.peek();
                    if(ch =='(') {
                        if (c == ')') {
                            a = 1;
                        }else{
                            return false;
                        }
                    }
                if(ch =='[') {
                    if (c == ']') {
                        a = 1;
                    }else{
                        return false;
                    }
                }
                if(ch =='{') {
                    if (c == '}') {
                        a = 1;
                    }else{
                        return false;
                    }
                }
                }
                if(a == 1){
                    stack.pop();
                }
            }

        if(stack.size() == 0 && i ==s.length()){
            return true;
        }
        return false;
    }*/

    public static void main03(String[] args) {
        String str= "([{)";
        System.out.println(isValid(str));
    }



    // 逆波兰 ----中序转为后序： https://leetcode.cn/problems/evaluate-reverse-polish-notation/
    public static int evalRPN(String[] tokens) {
        // 将输入中数据为 数字存入栈中
        Stack<Integer> stack=new Stack<>();

        for(String x:tokens){
            // 将字符串数据 转成整型 压入栈
            if( !(x.equals("+") || x.equals("-") || x.equals("*") ||x.equals("/") )){
                stack.push(Integer.parseInt(x));
            }else{
            int num2=stack.pop();
            int num1=stack.pop();
            switch(x) {
                // 将计算后的值压入栈 进行下次计算
                case "+":
                    stack.push(num1 + num2);
                    break;
                case "-":
                    stack.push(num1 - num2);
                    break;
                case "*":
                    stack.push(num1 * num2);
                    break;
                case "/":
                    stack.push(num1 / num2);
                    break;
              }
            }
        }
        return stack.pop();
    }

    public static void main02(String[] args) {
        String[] tokens={"2","1","+","3","*"};
        System.out.println(evalRPN(tokens));
    }



    public static void main01(String[] args) {
        Stack<Integer> stack=new Stack<>();
        stack.push(12);
        stack.push(23);
        stack.push(34);
        stack.push(45);

        System.out.println(stack.pop());
        System.out.println(stack.size());

        System.out.println(stack.pop());

        System.out.println(stack.peek());
        System.out.println(stack.peek());
    }
}
